package com.learn.finished;

/*
统计n以内素数总数
 */
public class SumPrimeNum {
    //用暴力算法一步步穷举所有结果
    public static int bf(int n) {
        int count = 0;
        for (int i = 2; i < n; i++) {
            count += isPrime(i) ? 1 : 0;

        }
        return count;
    }

    //但是如果研究此算法，可以发现，其实很多的数字重复判断了多次，例如2*3的结果，判断了多次
    //找到一个素数，进行倍增，2*2,2*3,2*4...，那么这些数都是要排除的结果
    public static int eratosthenes(int n){
        boolean [] isPrime=new boolean[n];
        //默认均为false，所以用false代表素数
        int count=0;
        for (int i = 2; i < n; i++) {
            if (!isPrime[i]) {
                //此处有没有可能传入4，然后count++，计算错误呢？
                //没有，当i=2的时候，进入下面的for循环时，2*2=4，已经将该位数排除出去了。
                count++;
                for (int j = i*i; j < n; j+=i) {
                    /*i=2,3,4
                    2*i,---2*2,2*3,2*4,2*5,2*6...
                    2*i,---2*3,2*4,2*4,2*5...
                    2*i,---2*4,2*5...
                    那么，还是会有重复计算的地方，改成i*i，不在最初的地方开始遍历，就可以从已经遍历过后的地方开始
                     */
//                for (int j = 2*i; j < n; j+=i) {
                    //j就是合数的标记位
                    isPrime[j]=true;
                }
            }
        }
        return count;
    }
    private static boolean isPrime(int i) {
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(eratosthenes(100));
    }
}
